#include<iostream>
using namespace std;
#include<vector>

class Solution {
public:
    vector<int>temp1,temp2;
    vector<int>ret;
    void mergesort(vector<int>&nums,int left,int right,vector<int>&index)
    {
        
        if(left>=right)
            return;
        int mid=(left+right)>>1;
        //[left,mid][mid+1,right]
        mergesort(nums,left,mid,index);
        mergesort(nums,mid+1,right,index);
        int cur1=left,cur2=mid+1,i=0,j=0;
        while(cur1<=mid&&cur2<=right)
        {
            if(nums[cur1]<=nums[cur2])
            {
                temp1[i++]=nums[cur2];
                temp2[j++]=index[cur2++];
            }        
            else
            {
                ret[index[cur1]]+=right-cur2+1;
                temp1[i++]=nums[cur1];
                temp2[j++]=index[cur1++];
            }   
        }
        while(cur1<=mid)
        {
            temp1[i++]=nums[cur1];
            temp2[j++]=index[cur1++];
        }
        while(cur2<=right)
        {
            temp1[i++]=nums[cur2];
            temp2[j++]=index[cur2++];
        }
        for(int i=left;i<=right;i++)
        {
            nums[i]=temp1[i-left];
            index[i]=temp2[i-left];
        }
           
    }
    vector<int> countSmaller(vector<int>& nums) {
        temp1.resize(nums.size());
        temp2.resize(nums.size());
        ret.resize(nums.size());
         vector<int> index(nums.size());
        for(int i=0;i<nums.size();i++)
        {
            index[i]=i;
        }
         mergesort(nums,0,nums.size()-1,index);
         return ret;
    }
};

int main()
{
    vector<int> v = { 5,2,6,1 };
    Solution s;
    s.countSmaller(v);
    return 0;
}